#include "kmp.h"
#include <iostream>


void compute_overlay(const string& pattern,int* overlay_function){
	size_t pattern_len = pattern.size();
	int i = 0;
	overlay_function[i] = -1;
	int j = -1;
	while (i < pattern_len){
		if (j == -1 || pattern[i] == pattern[j]){
			++i;
			++j;
			//overlay_function[i] = j;
			if (pattern[i] != pattern[j])
				overlay_function[i] = j;
			else 
				overlay_function[i] = overlay_function[j];
		}
		else
			j = overlay_function[j];
	}

	for (int i = 0; i < pattern_len; ++i)
		cout<<overlay_function[i]<<"__";
	cout<<endl;
}

 int kmp(const string& target,const string& pattern){
	int pattern_len = pattern.size();
	int target_len = target.size();
	int* overlay_function = new int[pattern_len];
	compute_overlay(pattern,overlay_function);
	int pattern_index = 0;
	int target_index = 0;
	while ((pattern_index < pattern_len) && (target_index < target_len)){
		//pattern_index = -1   的情况是到达了overlay_function 的根位置都没有发生匹配,直接换下一个
		//如果匹配的话，继续匹配下一个

		if (pattern_index == -1 || target[target_index] == pattern[pattern_index]){
			++pattern_index;
			++target_index;
		}
		else 
			pattern_index = overlay_function[pattern_index];
		
	}

	delete [] overlay_function;
	if (pattern_index == pattern_len)
		return target_index - pattern_len;
	else 
		return -1;

}
